{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 算法分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 算法设计的目标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 正确性。能正确执行预先规定的功能和性能要求。\n",
    "- 可使用性。方便的使用，也叫用户友好性。\n",
    "- 可读性。逻辑必须是清晰的、简单的、结构化的。\n",
    "- 健壮性。要求算法有很好的容错性，即提供异常处理，能够对不合理的数据进行检查，不经常出现异常中断或死机。\n",
    "- 高效率与低存储量需求。通常算法的效率主要指算法的执行时间。算法存储量指的是算法执行过程中所需的最大存储空间。效率与低存储量都与问题的规模有关。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 算法效率分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "算法中基本运算次数 T(n) 是问题规模 n 的某个函数 f(n)，记做："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$T(n) = O(f(n))$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "“O” 读作 “大O”， 是 order 的简写，意指数量级，它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "“O” 的形式定义为：若 f(n) 是正整数 n 的一个函数，则 $T(n) = O(f(n))$ 表示存在一个正的常数 M，使得当 $n \\ge n_0$ 时都满足 $|T(n)| \\le M|f(n)|$, 也就是只求出 T(n) 的最高阶，忽略其低阶项和常数项，可以简化计算又能比较客观地反映出当 n 很大时算法的时间性能。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$O(1) < O(\\log_2n) < O(n) < O(n\\log_2n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 算法存储空间分析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模 n 的函数，以数量级形式给出，记做：$$S(n) = O(g(n))$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
